#include <stdlib.h>
#include <stdio.h>

typedef char ElemType;
typedef struct BTNode {
    ElemType data;
    struct BTNode *lchild, *rchild;
    int ltag, rtag;
} BTNode, *BiTree;
void ThInOrder(BTNode * tb){
    BTNode * p=tb->lchild;    // p 指向根结点的左孩子结点
    while(p != tb) {
        while(p->ltag==0)p=p-> lchild;    // 找开始结点
        printf("%c",p-> data);             // 访问开始结点 p
        
        while(p->rtag==1 && p-> rchild !=tb) { // 右指针域指向直接后继且后继不是根
            p=p->rchild;    // 走向右子树
            printf("%c",p->data);    // 输出右子树根结点的值
        }
        
        p=p->rchild;
    }
}

// 创建新节点
BTNode* createNode(ElemType data) {
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    node->data = data;
    node->lchild = NULL;
    node->rchild = NULL;
    node->ltag = 0;  // 0表示指向子树，1表示指向线索
    node->rtag = 0;
    return node;
}

// 中序线索化二叉树
void InThread(BTNode* p, BTNode** pre) {
    if (p != NULL) {
        InThread(p->lchild, pre);  // 递归左子树线索化
        
        if (p->lchild == NULL) {   // 建立当前节点的前驱线索
            p->lchild = *pre;
            p->ltag = 1;
        }
        
        if (*pre != NULL && (*pre)->rchild == NULL) {  // 建立前驱节点的后继线索
            (*pre)->rchild = p;
            (*pre)->rtag = 1;
        }
        
        *pre = p;  // 标记当前节点成为刚刚访问过的节点
        InThread(p->rchild, pre);  // 递归右子树线索化
    }
}

// 创建中序线索二叉树
BTNode* CreateInThread(BTNode* root) {
    BTNode* thrt = createNode('#');  // 创建头节点
    thrt->ltag = 0;
    thrt->rtag = 1;
    
    if (root == NULL) {
        thrt->lchild = thrt;
    } else {
        thrt->lchild = root;
        BTNode* pre = thrt;
        InThread(root, &pre);
        
        pre->rchild = thrt;
        pre->rtag = 1;
        thrt->rchild = pre;
    }
    
    return thrt;
}

// 测试函数
void test_ThInOrder() {
    printf("=== 线索二叉树中序遍历测试 ===\n");
    
    // 创建一个示例二叉树
    //       A
    //      / \
    //     B   C
    //    / \   \
    //   D   E   F
    
    BTNode* root = createNode('A');
    root->lchild = createNode('B');
    root->rchild = createNode('C');
    root->lchild->lchild = createNode('D');
    root->lchild->rchild = createNode('E');
    root->rchild->rchild = createNode('F');
    
    printf("原始二叉树结构:\n");
    printf("       A\n");
    printf("      / \\\n");
    printf("     B   C\n");
    printf("    / \\   \\\n");
    printf("   D   E   F\n\n");
    
    // 创建线索化二叉树
    BTNode* threadTree = CreateInThread(root);
    
    printf("中序遍历结果: ");
    ThInOrder(threadTree);
    printf("\n");
    printf("期望结果: DBEACF\n\n");
    
    // 测试空树
    printf("测试空树:\n");
    BTNode* emptyThreadTree = CreateInThread(NULL);
    printf("空树中序遍历: ");
    ThInOrder(emptyThreadTree);
    printf("(无输出)\n\n");
    
    // 测试单节点树
    printf("测试单节点树:\n");
    BTNode* singleNode = createNode('X');
    BTNode* singleThreadTree = CreateInThread(singleNode);
    printf("单节点中序遍历: ");
    ThInOrder(singleThreadTree);
    printf("\n期望结果: X\n");
}

int main() {
    test_ThInOrder();
    return 0;
}